package com.arron.algorithm.huawei.中等;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class 购物单 {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        //表示多少钱
        int N = in.nextInt();
        //表示有多少个物品
        int m = in.nextInt();
//        int[][] goodsInfo = new int[m + 1][3];
        Goods[] goods= new Goods[m+1];
        for (int i = 1; i <= m; i++) {
            int v = in.nextInt();
            int p = in.nextInt();
            int q = in.nextInt();
            goods[i] = new Goods(i,v, p, q);
        }
        //初始化主件的附件id
        for (int i = 1; i <= m; i++) {
            if (goods[i].q > 0) {
                if (goods[goods[i].q].q1 == 0) {
                    goods[goods[i].q].q1 = goods[i].number;
                } else {
                    goods[goods[i].q].q2 = goods[i].number;
                }
            }
        }

        //表示选择的m个物品，花费N元的最大满意度
        int[][] dp = new int[m + 1][N + 1];


        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= N; j++) {
                if (j - goods[i].v < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //判断这个物品是否是附件
                    if (goods[i].q != 0) {
                        //如果是附件，则不做处理，在主件做处理
                        dp[i][j] = dp[i - 1][j];

                    } else {
                        //如果是主件，则依次判断是否有附件1，附件2
                        int v,v1=0,v2=0,v3=0;
                        int t,t1=0,t2=0,t3=0;
                        //购买主件的钱
                        v = goods[i].v;
                        //购买主件的满意度
                        t= v*goods[i].p;
                        //购买主件+附件1
                       if (goods[i].q1 !=0){
                           v1 = v+goods[goods[i].q1].v;
                           t1 = t+goods[goods[i].q1].p*goods[goods[i].q1].v;
                       }
                       //购买主件+附件2
                        if (goods[i].q2 !=0){
                            v2 = v+goods[goods[i].q2].v;
                            t2=t+goods[goods[i].q2].p*goods[goods[i].q2].v;
                        }
                        //购买主件+附件1+附件2
                        if (goods[i].q2 !=0 && goods[i].q1 !=0){
                            v3 = v+goods[goods[i].q1].v+goods[goods[i].q2].v;
                            t3=t+goods[goods[i].q2].p*goods[goods[i].q2].v+goods[goods[i].q1].p*goods[goods[i].q1].v;
                        }

                        if (j - v < 0) {
                            //钱不够买，则还是继承上一个物品的最大满意度
                            dp[i][j] = dp[i - 1][j];
                        } else {
                            //只购买主件
                            dp[i][j] = Math.max( dp[i - 1][j],dp[i - 1][j-v]+t);
                            //购买主件+附件1
                            if (j>=v1 && v1!=0){
                                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j-v1]+t1);
                            }
                            //购买主件+附件2
                            if (j>=v2 && v2!=0){
                                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j-v2]+t2);
                            }
                            //购买主件+附件1+附件2
                            if (j>=v3 && v3!=0){
                                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j-v3]+t3);
                            }
                        }
                    }
                }
            }
        }

        System.out.print(dp[m][N]);


    }
 static    class Goods {

        int v; // 价格
        int p; //重要程度
        int q; //是否是主件
        int number; //自己的编号

        int q1;//附件1
        int q2; //附件2

        public Goods(int n,int v,int p,int q){
            this.v=v;
            this.number=n;
            this.p=p;
            this.q=q;
        }



    }


}
